`
https://leetcode.cn/problems/beautiful-arrangement/
`

/**
 * @param {number} n
 * @return {number}
 */
var countArrangement = function (n) {
  // 记录所有的「优美排列」的个数
  let res = 0
  // 记录回溯算法的递归路径，即每个索引选择的元素
  const track = []
  // track 中的元素会被标记为 true，避免重复选择
  const used = new Array(n + 1).fill(false)

  const backtrack = (index) => {
    if (index > n) {
      res++
      return
    }

    // 索引 index 开始选择元素
    for (let i = 1; i <= n; i++) {
      //  这个数字用过了
      if (used[i]) {
        continue
      }

      // 不符合优美排列
      if (i % index !== 0 && index % i !== 0) {
        continue
      }

      used[i] = true
      track.push(i)
      backtrack(index + 1)
      track.pop()
      used[i] = false
    }
  }

  backtrack(1)

  return res
};